#include <stdio.h>
#include "seqlist.h"
#include "linklist.h"
#include "circlelist.h"
#include "stdlib.h"
#include "string.h"
#include "memwatch.h"
#include "duallist.h"
#include "stack.h"
#include "linkstack.h"
#include "tree.h"
#include "sorter.h"



int main(int argc, char *argv[])
{
    int arr[]={3,2,9,1,223,34,39,43,12,21,4,1,8,9};
//    myinsertSorter(arr,6);
//    shellSort(arr,sizeof(arr)/sizeof(int));
    mergeSortExt(arr,sizeof(arr)/sizeof(int));
    return 0;
}
int crossTree(DblNode* root);
int crossTreeAfter(DblNode* root);
int crossTreeMid(DblNode* root);
int countLeaf(DblNode* root);
int countLeafDeep(DblNode* root);
int copyTree(DblNode* src,DblNode** dst);
int freeTree(DblNode** root);
int crossTreeWithoutRecursive(DblNode* root);





int mainTree(int argc, char *argv[])
{
    DblNode rlrl;
    rlrl.data='D';
    rlrl.leftChild=NULL;
    rlrl.rightChild=NULL;

    DblNode rlrr;
    rlrr.data='E';
    rlrr.leftChild=NULL;
    rlrr.rightChild=NULL;

    DblNode rlr;
    rlr.data='C';
    rlr.leftChild=&rlrl;
    rlr.rightChild=&rlrr;

    DblNode rl;
    rl.data='B';
    rl.rightChild=&rlr;
    rl.leftChild=NULL;

    DblNode rrrl;
    rrrl.data='H';
    rrrl.leftChild=NULL;
    rrrl.rightChild=NULL;

    DblNode rrr;
    rrr.data='G';
    rrr.rightChild=NULL;
    rrr.leftChild=&rrrl;

    DblNode rr;
    rr.data='F';
    rr.rightChild=&rrr;
    rr.leftChild=NULL;




    DblNode root;
    root.data='A';
    root.leftChild=&rl;
    root.rightChild=&rr;

    crossTree(&root);
    printf("\n");
    crossTreeMid(&root);
    printf("\n");
    crossTreeAfter(&root);
    printf("\n");
    int count=countLeaf(&root);
    printf("total leaf:%d\n",count);
    count=countLeafDeep(&root);
    printf("total deep:%d\n",count);

    printf("copying tree...\n");
    DblNode **copyDst=malloc(sizeof(DblNode*));
    copyTree(&root,copyDst);
    crossTree(*copyDst);
    freeTree(copyDst);
    free(copyDst);
    printf("cross without recursive");
    crossTreeWithoutRecursive(&root);
    return 0;
}

DblNode* findLeft(DblNode* node,LinkStack* ls){
    if(node==NULL){
        return NULL;
    }
    while(node->leftChild!=NULL){
        LinkStack_Push(ls,node);
        node=node->leftChild;
    }
    return node;
}

int crossTreeWithoutRecursive(DblNode* root){
    LinkStack *stack = LinkStack_Create();
    if(root==NULL){
        return 0;
    }
    DblNode* pnode=findLeft(root,stack);
    while(pnode){
        printf("%c",pnode->data);
        if(pnode->rightChild!=NULL){
            pnode=findLeft(pnode->rightChild,stack);
        }else{
            if(LinkStack_Size(stack)>0){
                pnode=LinkStack_Pop(stack);

            }else{
                return 0;
            }
        }

    }

}

/**
 * @brief freeTree 释放树节点
 * @param root
 * @return
 */
int freeTree(DblNode** root){
    //判断节点是不是NULL
    if(*root==NULL){
        return 0;
    }
    DblNode* node=*root;
    printf("freenode:%c\n",node->data);
    fflush(stdout);
    freeTree(&(node->leftChild));
    freeTree(&(node->rightChild));
    free(node);
    return 0;
}


int copyTree(DblNode* src,DblNode** dst){
    if(src==NULL){
        return 0;
    }
    DblNode* dstd=malloc(sizeof(DblNode));
    memset(dstd,0,sizeof (DblNode));
    copyTree(src->leftChild,&(dstd->leftChild));
    copyTree(src->rightChild,&(dstd->rightChild));
    dstd->data=src->data;
    *dst=dstd;
    return 0;
}

/**
 * @brief countLeaf 计算树的深度
 * @param root
 * @return
 */
int countLeafDeep(DblNode* root){
    if(root==NULL){
        return 0;
    }
    //前序遍历
    int countleft=countLeaf(root->leftChild);
    int countRight=countLeaf(root->rightChild);
    if(root->leftChild==NULL&&root->rightChild==NULL){
        return 1;
    }else{
        return countleft>countRight?countleft+1:countRight+1;
    }
}

/**
 * @brief countLeaf 计算叶子数量
 * @param root
 * @return
 */
int countLeaf(DblNode* root){
    if(root==NULL){
        return 0;
    }
    //前序遍历
    int countleft=countLeaf(root->leftChild);
    int countRight=countLeaf(root->rightChild);
    if(root->leftChild==NULL&&root->rightChild==NULL){
        return 1;
    }else{
        return countleft+countRight;
    }
}


/**
 * @brief crossTree 遍历树的语法
 * @return
 */
int crossTree(DblNode* root){
    if(root==NULL){
        return 0;
    }
    //前序遍历
    printf("%c",root->data);
    crossTree(root->leftChild);
    crossTree(root->rightChild);
    return 0;
}
int crossTreeMid(DblNode* root){
    if(root==NULL){
        return 0;
    }
    //前序遍历
    crossTreeMid(root->leftChild);
    printf("%c",root->data);
    fflush(stdout);
    crossTreeMid(root->rightChild);
    return 0;
}

int crossTreeAfter(DblNode* root){
    if(root==NULL){
        return 0;
    }
    //前序遍历
    crossTreeAfter(root->leftChild);
    crossTreeAfter(root->rightChild);
    printf("%c",root->data);
    return 0;
}

typedef struct LLNode LLNode;

struct LLNode{
    LinkListNode node;
    int type;//类似0 数字 1符号
    void* val;
};

/**
 * @brief splitFormular 切割表达式
 * @param formular
 * @return
 */
LinkList* splitFormular(char *formular){
    LinkList* ll=LinkList_Create();
    char* pointer=formular;
    int prevType=-1;//表示当前是数字还是符号 0 数字， 1 符号
    int prevVal=0;
    while(*pointer!='\0'){
        if(*pointer>='0'&&*pointer<='9'){
            if(prevType==0){
                //如果前面那位是数字，那么久相加
                prevVal=prevVal*10+(*pointer-'0');
            }else{
                prevVal=(*pointer-'0');
            }
            prevType=0;
        }else if(*pointer=='+' ||*pointer=='-'
                 ||*pointer=='*' ||*pointer=='/'
                 ||*pointer=='(' ||*pointer==')'){
            if(prevType==0){
                //入栈加重置
                LLNode *node=malloc(sizeof(LLNode));
                node->val=(void*)prevVal;
                node->type=0;
                LinkList_Insert(ll,(LinkListNode*)node,LinkList_Length(ll));
            }

            LLNode *node=malloc(sizeof(LLNode));
            node->val=(void*)*pointer;
            node->type=1;
            LinkList_Insert(ll,(LinkListNode*)node,LinkList_Length(ll));

            prevType=1;
            prevVal=0;

        }else if(*pointer==' '){
            //prevType=1;
            //prevVal=0;
        }

        pointer++;
    }
    if(prevVal!=0&&prevType==0){
        LLNode *node=malloc(sizeof(LLNode));
        node->val=(void*)prevVal;
        node->type=0;
        LinkList_Insert(ll,(LinkListNode*)node,LinkList_Length(ll));
    }
//    while (LinkList_Length(ll)>=0) {
//        LLNode* node=(LLNode*)LinkList_Delete(ll,0);
//        if(node->type==0){
//            printf("%d",node->val);
//        }else{
//            printf("%c",node->val);
//        }
//        printf(",");
//        fflush(stdout);
//        free(node);
//    }
//        printf("\n");

//    LinkList_Destory(ll);
    return ll;
}

int checkDeg(char cl,char lr);


/**
 * @brief converter 转换
 * @param ll
 * @return
 */
LinkList* converter(LinkList* ll){
    LinkStack *ls=LinkStack_Create();
    //连续2位数字才可以进栈
    LinkList *llnew=LinkList_Create();

    while(LinkList_Length(ll)>0){
        LLNode* lnode=(LLNode*)LinkList_Delete(ll,0);
        void* data=lnode->val;

        if(lnode->type==0){
            LLNode *node=(LLNode*)malloc(sizeof (LLNode));
            node->type=0;
            node->val=lnode->val;
            LinkList_Insert(llnew,(LinkListNode*)node,LinkList_Length(llnew));
        }else if(lnode->type==1){
            char point=(char)data;
            if(point=='('){
                LinkStack_Push(ls,point);
            }else if(point==')'){
                void* ch=NULL;
                while(ch==NULL||(char)ch!='('){
                    //如果遇到右括号，一直弹出直到遇到左括号
                    ch=LinkStack_Pop(ls);
                    if((char)ch=='('){
                        break;
                    }
                    LLNode *node=(LLNode*)malloc(sizeof (LLNode));
                    node->type=1;
                    node->val=ch;
                    if(ch!=')'){

                        LinkList_Insert(llnew,(LinkListNode*)node,LinkList_Length(llnew));
                    }
                }
            }else if(point=='+'
                    || point=='-'
                    || point=='*'
                    || point=='/'
                    || point=='%'
                    ){
                while(1){

                void *ch=LinkStack_Top(ls);
                //如果栈顶元素优先级别低，入栈
                if(ch==NULL){
                    LinkStack_Push(ls,point);
                    break;
                }else{
                    //如果栈顶低，直接入栈
                    if(checkDeg((char)ch,point)==0){
                        LinkStack_Push(ls,point);
                        break;
                    }else{
                        //出栈.后继续对比
                        void *chtmp=LinkStack_Pop(ls);
                        LLNode *node=(LLNode*)malloc(sizeof (LLNode));
                        node->type=1;
                        node->val=chtmp;
                        LinkList_Insert(llnew,(LinkListNode*)node,LinkList_Length(llnew));
                    }
                }
                }

            }

        }
        free(lnode);
    }
    while(LinkStack_Size(ls)>0){
        char *ch=LinkStack_Pop(ls);
        LLNode *node=(LLNode*)malloc(sizeof (LLNode));
        node->type=1;
        node->val=(void*)ch;
        LinkList_Insert(llnew,(LinkListNode*)node,LinkList_Length(llnew));
    }
//    while(LinkList_Length(llnew)>0){
//        LLNode* node=(LLNode*)LinkList_Delete(llnew,0);
//        if(node->type==0){
//            printf("%d",node->val);
//        }else{
//            printf("%c",node->val);
//        }
//        free(node);
//    }
    printf("\n");
    LinkStack_Destroy(ls);
    LinkList_Destory(ll);
    return llnew;
}

int getDeg(char ch);

int checkDeg(char cl,char lr){
    if(getDeg(cl)>=getDeg(lr)){
        //左高或等于右
        return 1;
    }else{

        //栈顶元素低
        //左小于右边
        return 0;
    }
    return 0;
}



int getDeg(char ch){
    int deg=0;
    if(ch=='+'||ch=='-'){
        deg=0;
    }else if(ch=='*'||ch=='/'){
        deg=1;
    }else if(ch=='('){
        deg=-1;
    }
    return deg;
}


double calc(LinkList* list){
    LinkStack *ls = LinkStack_Create();
    while(LinkList_Length(list)>0){
        LLNode* node=LinkList_Delete(list,0);
        if(node->type==0){
            LinkStack_Push(ls,node->val);
            fflush(stdout);
        }else if(node->type==1){
            fflush(stdout);
            int rightVal=LinkStack_Pop(ls);
            int leftVal=LinkStack_Pop(ls);
            int rst=0;
            switch((char)node->val){
            case '+':
                rst=leftVal+rightVal;
                break;
            case '-':
                rst=leftVal-rightVal;
                break;
            case '*':
                rst=leftVal*rightVal;
                break;
            case '/':
                rst=leftVal/rightVal;
                break;
            }
            LinkStack_Push(ls,rst);
        }
        free(node);
    }
    int rst=LinkStack_Pop(ls);
    printf("result is:%d",rst);
    return 0.0;
}


int mainCalc(int argc, char *argv[])
{
    //1.先把数据拆分成为各个单元的链表
    char *formular="9 + (83 - 1) * 5 + 8 / 2";
    printf("执行方程%s\n",formular);
    LinkList *ll = splitFormular(formular);
    LinkList *l2=converter(ll);
    double rst=calc(l2);
    //
    return 0;
}

typedef struct Result Result;
struct Result{
    int resCode;
    char reason[200];
};

/**
 * @brief checkCode 检查代码的合法性
 * @param code
 * @return
 */
Result checkCode(char *code){
    Result rst={0,""};
    char* point=code;
    LinkStack *ls = LinkStack_Create();
    if(ls!=NULL){
        while(*point!='\0'){
            printf("%c",*point);
            char tmp=*point;
            if(tmp=='<' ||tmp=='{'
                    ||tmp=='[' ||tmp=='('
                    ||tmp=='"' ||tmp=='\'' ){
                LinkStack_Push(ls,point);
                point++;

                continue;
            }
            if(tmp=='>' ||tmp=='|'
                    ||tmp=='}'
                    ||tmp==']' ||tmp==')'
                    ||tmp=='"' ||tmp=='\'' ){
                char* ch=LinkStack_Pop(ls);
                if(ch==NULL){
                    rst.resCode=300;
                    sprintf(rst.reason,"位置%d的字符%c无法找到匹配项目",(int)(point-code),*point);
                    break;
                }
//                printf("执行pop:%c匹配tmp:%c\n",*ch,tmp);
                if(*ch=='<'&&tmp!='>'){
                    rst.resCode=300;
                    sprintf(rst.reason,"位置%d的字符%c无法找到匹配项目",(int)(point-code),*point);
                    break;
                }else  if(*ch=='{'&&tmp!='}'){
                    rst.resCode=300;
                    sprintf(rst.reason,"位置%d的字符%c无法找到匹配项目",(int)(point-code),*point);
                    break;
                }else  if(*ch=='('&&tmp!=')'){
                    rst.resCode=300;
                    sprintf(rst.reason,"位置%d的字符%c无法找到匹配项目",(int)(point-code),*point);
                    break;
                }else  if(*ch=='['&&tmp!=']'){
                    rst.resCode=300;
                    sprintf(rst.reason,"位置%d的字符%c无法找到匹配项目",(point-code),*point);
                    break;
                }else  if(*ch=='"'&&tmp!='"'){
                    rst.resCode=300;
                    sprintf(rst.reason,"位置%d的字符%c无法找到匹配项目",(point-code),*point);
                    break;
                }else  if(*ch=='\''&&tmp!='\''){
                    rst.resCode=300;
                    sprintf(rst.reason,"位置%d的字符%c无法找到匹配项目",(point-code),*point);
                    break;
                }

            }
            point++;
        }
        printf("执行最后的判断");

        fflush(stdout);
        //在全部判断完成之后，我们还需要判断栈是否还有元素
        if(LinkStack_Size(ls)>0){
            printf("link stack still not empty\n");
            rst.resCode=300;
            char tmp[100]={0};
            while (LinkStack_Size(ls)>0) {
                char *ch=LinkStack_Pop(ls);
                char arr[2]={*ch,0};

                strcat(tmp,arr);
                strcat(tmp,",");
            }
            sprintf(rst.reason,"存在无法匹配的字符串%s",tmp);
        }

    }
    return rst;
}
int mainCodeChecker(int argc, char *argv[])
{
    char* code="#include <stdio.h> int main({ int a[4][4]; int (*p)[4]; p = a[0]; return 0;}";
    //检查代码的合法性
    Result rst=checkCode(code);
    printf("\n返回码是:%d \n返回原因是:%s\n",rst.resCode,rst.reason);
    return 0;
}


int mainLinkStack(int argc, char *argv[])
{
    LinkStack *s = LinkStack_Create();
    for(int i=0;i<50;i++){
        LinkStack_Push(s,i);
    }
    while(Stack_Size(s)>0){
        int popV = LinkStack_Pop(s);
        printf("%d ",popV);
    }
    LinkStack_Destroy(s);
    return 0;
}


int mainStack(int argc, char *argv[])
{
    Stack* s=Stack_Create();
    for(int i=0;i<5;i++){
        Stack_Push(s,i);
    }
    while(Stack_Size(s)>0){
        int popV = Stack_Pop(s);
        printf("%d",popV);
    }
    Stack_Destroy(s);
    return 0;
}

typedef struct DualNodeWrapper DualNodeWrapper;

struct DualNodeWrapper{
    DualLinkNode node;
    int val;
};

int mainDual(int argc, char *argv[])
{

    DualLink* dl=NULL;
    dl = DualLink_Create();

    for(int i=0;i<10;i++){
        DualNodeWrapper* dnw=(DualNodeWrapper*)malloc(sizeof (DualNodeWrapper));
        dnw->val=i;
        DualLink_Insert(dl,dnw,0);
        printf("the list size:%d \n",DualLink_Length(dl));
    }
//    while(DualLink_Length(dl)>0){
//        DualNodeWrapper *deleted = DualLink_Delete(dl,0);
//        printf("%d ",deleted->val);
//        free(dl);
//    }
    while(DualLink_Length(dl)>0){
        DualNodeWrapper *current = DualLink_Current(dl);
        DualLink_Next(dl);
        DualLink_DeleteNode(dl,current);
        printf("%d ",current->val);
    }

    printf("\n");
    DualLink_Destroy(dl);

    return 0;
}

typedef struct CirNodeWrapper CirNodeWrapper;
struct CirNodeWrapper{
    CircleListNode node;
    int val;
};
int mainCir(int argc, char *argv[])
{
    mwInit();
    CircleList *list = CircleList_Create();
    for(int i=0;i<10;i++){
        CirNodeWrapper* cnw=(CirNodeWrapper*)malloc(sizeof(CirNodeWrapper));
        cnw->val=i;
        CircleList_Insert(list,cnw,0);
        printf("sizeof clist:%d\n",CircleList_Length(list));
    }
    for(int i=0;i<10;i++){
        CirNodeWrapper *node = (CirNodeWrapper*)CircleList_Get(list,i);
        printf("%d ",node->val);
    }
    printf("\n");
    while (CircleList_Length(list)>0) {
        CirNodeWrapper *node = CircleList_Delete(list,0);
        printf("%d",node->val);
        free(node);
    }

    for(int i=0;i<10;i++){
        CirNodeWrapper* cnw=(CirNodeWrapper*)malloc(sizeof(CirNodeWrapper));
        cnw->val=i;
        CircleList_Insert(list,cnw,0);
        printf("sizeof clist:%d\n",CircleList_Length(list));
    }
    printf("\n 执行迭代\n");
    CircleList_Destroy(list);
    while(CircleList_Length(list)>0){
        CirNodeWrapper *crnw = CircleList_Current(list);
        printf("%d ",crnw->val);
        CircleList_Next(list);
        CircleList_DeleteNode(list,crnw);
    }
    mwTerm();

    return 0;
}


typedef struct NodeWrapper NodeWrapper;
struct NodeWrapper{
    LinkListNode node;
    int val;
};

int main_Link(int argc, char *argv[])
{
    LinkList *list = LinkList_Create();
    for(int i=0;i<10;i++){
        NodeWrapper* nw=(NodeWrapper*)malloc(sizeof(NodeWrapper));
        nw->val=i;
        LinkList_Insert(list,nw,LinkList_Length(list));
    }
    printf("len:%d\n",LinkList_Length(list));
    while(LinkList_Length(list)>0){
        NodeWrapper* nw=(NodeWrapper*)LinkList_Delete(list,0);
        printf("%d ",nw->val);
        free(nw);
    }
    printf("\n");
    LinkList_Destory(list);
    return 0;
}

int mainiSeq()
{
    SeqList *handle = SeqList_Create(10);
    for(int i=0;i<10;i++){
        //存储实际值，也可以存储地址值
        SeqList_Insert(handle,(SeqListNode*)i,0);
    }

    printf("\n");
    for(int i=0;i<10;i++){
        int val = (int)SeqList_Get(handle,i);
        printf("%d ",val);
    }
    printf("\n");

    printf("sizeof list:%d\n",SeqList_Length(handle));
    SeqList_Delete(handle,7);
    for(int i=0;i<10;i++){
        int val = (int)SeqList_Get(handle,i);
        printf("%d ",val);
    }
    printf("\n");
    printf("sizeof list:%d\n",SeqList_Length(handle));
//    while(SeqList_Length(handle)>0){
//        int val=(int)SeqList_Delete(handle,0);
//        printf("%d",val);
//    }


    SeqList_Destory(handle);
    return 0;
}
